package C035;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * ClassName: C06
 * Package: C035
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/1/8 15:10
 * @Version 1.0
 * @Since 1.0
 */
public class C06 {
    public static void main(String[] args) {

    }
    static class FreqStack {

        // 层数表
        List<ArrayList<Integer>> cntValue = new ArrayList<>();
        // 词频表
        HashMap<Integer, Integer> valuesTime = new HashMap<>();
        // 最高出现的次数
        int maxTime;

        public FreqStack() {

        }

        public void push(int val) {
            int curValueTime = 0;
            // 出现次数+1
            if (!valuesTime.containsKey(val)) {
                valuesTime.put(val, 1);
                curValueTime = 1;
            }else {
                valuesTime.put(val, valuesTime.get(val) + 1);
                curValueTime = valuesTime.get(val);
            }

            // 层数表更新
            if(cntValue.size() < curValueTime) {
                cntValue.add(new ArrayList<Integer>());
            }
            cntValue.get(curValueTime - 1).add(val);

            // 最大出现次数更新
            maxTime = Math.max(maxTime, curValueTime);
        }

        public int pop() {
            // 更新层数表
            ArrayList<Integer> maxCnt = cntValue.get(maxTime - 1);
            Integer res = maxCnt.remove(maxCnt.size() - 1);
            if(maxCnt.isEmpty()) {
                cntValue.remove(maxCnt);
                maxTime --;
            }

            // 更新最大次数
            valuesTime.put(res, valuesTime.get(res) - 1);

            if(valuesTime.get(res) == 0) {
                cntValue.remove(res);
            }
            return res;
        }
    }


}
